//438.找到字符串中所有字母异位词
#include<iostream>
#include<string>
#include<vector>
#include<unordered_map>
using namespace std;

vector<int> findAnagrams(string s,string p){
    //定义两个哈希表分别用来存储两个字符串,建立字符和字符个数的映射关系
    unordered_map<char, int> hashs;
    unordered_map<char, int> hashp;
    //定义一个数组用来存储结果
    vector<int> v;

    //定义左右指针
    int left=0,right=0;
    //定义一个变量用来记录字符的有效个数
    int count = 0;

    for(auto e : p){
        hashp[e]++;
    }

    while(right<s.size()){
        //进窗口
        hashs[s[right]]++;
        //如果哈希表s中存放字符个数小于哈希表p中的个数，count加一
        if(hashs[s[right]]<=hashp[s[right]]){
            count++;
        }

        //判断条件
        if(right-left+1>p.size()){
            //出窗口
            if(hashs[s[left]]<=hashp[s[left]]){
                count--;
            }
            hashs[s[left]]--;
            if(hashs[s[left]]==0){
                hashs.erase(s[left]);
            }
            left++;
        }

        //更新结果
        if(count==p.size()){
            v.push_back(left);
        }

        right++;
    }

    return v;
}

int main(){
    string s = {"cbaebabacd"};
    string p = {"abc"};

    vector<int> v=findAnagrams(s,p);
    for(auto e : v){
        cout << e << " ";
    }
    cout << endl;
    return 0;
}